1. Field of Invention
This invention relates to Content Addressable Memories (CAM) used in data compression and robotics applications.
2. Description of Prior Art
Content Addressable Memories (CAM) are known since the early 1960's and several integrated chip sets are commercially available (examples are the AMD99C10 chips from Advanced Micro Devices and the MU9C1640 CasheCAM chip from MUSIC Semiconductors).
A CAM is usually defined as a device in which a binary data input pattern is compared with all the stored data words to find a matching binary pattern. The locations, if any, at which a matching data word is found then generates a binary output address code to indicate where the matching data pattern is stored. An additional MATCH output line may indicate of whether or not a matching pattern was found in the CAM. If several matching data words are found then a priority scheme may select one of the locations as the output address code. An alternate method would serially scan a normal Random Addressable Memory (RAM) to find a matching data pattern, but such solution would be too slow for most applications. Sorting the stored data words in a HASH code scheme for more rapid searching is still not fast enough for most applications. A forward pointing data tree (first described by Edward Sussenguth: reference: "Use of Tree Structures for Processing Files" Communications of the ACM, May 1963) is used to speed up memory searching in the international V.42bis compression standard for modems. This scheme is fast enough for data compression in modems but still not fast enough for data or image compression in modern high speed networks. Another common option is to swap the data input and the address input on a normal Random Addressable Memory (RAM) so that the memory is in effect addressed by the data word. The output address would then be stored as the data in the memory. This solution would require a huge memory capacity where most memory locations would remain unused. All of these solutions are unsatisfactory for application in high speed data compression and robotics.
Before a CAM can be used it must be pre-loaded with binary data words. Using normal Random Addressable Memory cells would require enormous power consumption for the anticipated applications. This would severely limit the practical memory capacity of the CAM and require a re-loading of the memory after every power down. In fact using any type of logic gates for storage or internal pattern comparison would consume so much power as to be unacceptable for very large CAM devices. An alternative is to use non volatile pattern storage such as: "Fuses" used in Programmable Read Only Memories (PROM); "Antifuses" used in Field Programmable Gate Arrays (FPGAs); or buried charges in the chip substrate known as FLUSH, EPROM, EEPROM or Ferro-electric (PLZT) technologies. The data pattern can also be incorporated into the original chip layout or deposited later by laser beams through transparent chip covers. Some of these known technologies allow for memory erasing and later re-programming.
In 1975 the inventor Klaus Holtz first described self learning networks in a patent application which later lead to U.S. Pat. No. 4,366,551. A first publication "Here comes the brain-like, self-learning, no-programming, computer of the future" appeared in the proceedings of "The First West Coast Computer Faire 1977". This research has meanwhile evolved into a new science called "Autosophy" and a new information theory which includes six known learning modes or "Omni Dimensional Networks". The new information theory is best described in a paper "Hyperspace storage compression for Multimedia systems" (IS&T/SPIE Electronic Imaging: Science and Technology Paper 2188-40) published in February 1994. One of the learning modes, the serial tree networks, are implemented in the CCITT V.42bis data compression standard which is now included in virtually all new modem designs. Tree network data compression can sometimes double the speed of transmission in modems or communications networks. The most recent references can be found in the proceedings of SuperCon96 "Data Compression in Network Design" and "Digital Image and Video Compression for Packet Networks". Similar learning modes, including the "Parallel Omni Dimensional Networks" are now being used for image and video compression. In the near future brain-like self-learning "Autosopher" may largely replace the programmed data processing computer. Self-learning and no-programming robots are now being developed.
To design and build the new self-learning Autosophy robots, including data or image compression, requires very large and inexpensive Content Addressable Memories (CAM) with features far in excess to what is now known or available. These new memory devices should have at least the following features:
1. Storage capacities should be very large and able to grow into Tera Bit ranges. PA0 2. It should be very compact and robust to fit into small mobile robots or portable systems. PA0 3. It must consume extreme little power for use in solar or battery driven systems. PA0 4. It should be non volatile and retain its information at power-off. PA0 5. It should be very inexpensive and include methods for self-repair. PA0 6. Memory search access should be very fast and in the tens of nano second range. PA0 7. Memory loading and learning may proceed during systems operations. PA0 8. The devices could be erasable and re-programmable for recycling in other systems.
An attempt to provide very large and low power CAMs was previously disclosed in the Yoneda U.S. Pat. No. 5,388,065. This method uses a storage trait to define a connection, or non connection, between a first data line and an internal match line and a second storage unit defining the connection, or non connection, between a second data line to the match line using a control word line. The storage units can be composed of couplers such as non volatile memory elements like PROM, EPROM, EEPROM or UVE-PROM. While superficially resembling some aspects of the present invention the CAM function is implemented in a totally different way including a match line and control word lines which are not found in the present invention. The operation is dynamic and requires sensing of pulses on the match line while the present invention is static and requires no internal clocking.
Hashimoto in U.S. Pat. No. 5,329,488 discloses a non volatile semiconductor memory which replaces defective memory cells with redundant cells. This invention is not a Content Addressable Memory.
Ohri in U.S. Pat. No. 5,301,143 discloses a method of reading the state of internal fuses using external addresses. This is not a Content Addressable Memory using multiple bit output address codes.